package com.huangyi;

import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void main(String[] args) {
        //岛屿数量
        class Solution {
            int[] dx = {0, 0, 1, -1};
            int[] dy = {1, -1, 0, 0};
            int m, n;
            Queue<int[]> q = new LinkedList<>();
            boolean[][] vis;
            int ret;

            public int numIslands(char[][] grid) {
                m = grid.length;
                if (m == 0) return 0;            // 先判空，再取 n
                n = grid[0].length;

                vis = new boolean[m][n];
                ret = 0;

                for (int i = 0; i < m; i++) {
                    for (int j = 0; j < n; j++) {
                        if (grid[i][j] == '1' && !vis[i][j]) {
                            bfs(grid, i, j);    // 一次 BFS 吞并一整块岛
                        }
                    }
                }
                return ret;
            }

            // BFS：以 (si, sj) 为起点吞并整块岛屿
            public void bfs(char[][] grid, int si, int sj) {
                q.clear();                       // 成员队列：显式清空更稳妥
                q.offer(new int[]{si, sj});
                vis[si][sj] = true;              // 入队前/时标记，避免重复入队

                while (!q.isEmpty()) {
                    int[] cur = q.poll();
                    int a = cur[0], b = cur[1];

                    for (int k = 0; k < 4; k++) {
                        int x = a + dx[k], y = b + dy[k];
                        if (x >= 0 && x < m && y >= 0 && y < n
                                && !vis[x][y] && grid[x][y] == '1') {
                            vis[x][y] = true;     // 先标记，再入队
                            q.offer(new int[]{x, y});
                        }
                    }
                }
                ret++;                            // 本轮 BFS 结束 → 发现了一座岛
            }
        }


        //岛屿的最大面积
        class Solution2 {
            Queue<int[]> q = new LinkedList<>(); // 成员队列，BFS 开始时清空更稳妥
            int m, n;
            boolean[][] vis;
            int[] dx = {0, 0, 1, -1};
            int[] dy = {1, -1, 0, 0};

            public int maxAreaOfIsland(int[][] grid) {
                m = grid.length;
                if (m == 0) return 0;        // 先判空，避免 NPE
                n = grid[0].length;
                vis = new boolean[m][n];

                int ret = 0, cur = 0;
                for (int i = 0; i < m; i++) {
                    for (int j = 0; j < n; j++) {
                        if (grid[i][j] == 1 && !vis[i][j]) {
                            cur = 0;                         // 可有可无，这里保持你的风格
                            int tmp = bfs(grid, i, j, cur);  // BFS 返回本岛面积
                            ret = Math.max(ret, tmp);
                        }
                    }
                }
                return ret;
            }

            // BFS 吞并以 (si, sj) 为起点的整座岛，返回其面积
            public int bfs(int[][] grid, int si, int sj, int cur) {
                q.clear();                     // 成员队列，使用前先清空
                q.offer(new int[]{si, sj});
                vis[si][sj] = true;

                while (!q.isEmpty()) {
                    int[] num = q.poll();
                    int a = num[0], b = num[1];
                    cur++;                     // 出队即计数，保证每格计一次

                    for (int i = 0; i < 4; i++) {
                        int x = a + dx[i], y = b + dy[i];
                        if (x >= 0 && x < m && y >= 0 && y < n
                                && grid[x][y] == 1 && !vis[x][y]) {
                            vis[x][y] = true;          // 入队前标记
                            q.offer(new int[]{x, y});  // 入队邻居坐标
                        }
                    }
                }
                return cur;
            }
        }
    }
}